package leetcode.Hot100;

import java.util.Arrays;

/**
 * @author Cheng Jun
 * Description: 给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
 * 请你找出符合题意的 最短 子数组，并输出它的长度。
 * 链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
 * @version 1.0
 * @date 2021/11/28 22:10
 * 输入：nums = [2,6,4,8,10,9,15]
 * 输出：5
 * 解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
 */
public class findUnsortedSubarray {

    public static void main(String[] args) {
        System.out.println(findUnsortedSubarray(new int[]{2, 6, 4, 8, 10, 9, 15}));
    }

    // 暴力解法 
    static int findUnsortedSubarray(int[] nums) {
        int[] numsCopy = Arrays.copyOf(nums, nums.length);
        Arrays.sort(numsCopy);
        // head 数组下标对应的元素 第一次不一致
        int head = 0;
        // head 数组下标对应的元素 最后依次不一致
        int tail = 0;
        int counter = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != numsCopy[i]) {
                if (counter == 0) {
                    head = i;
                    counter++;
                } else {
                    tail = i;
                }
            }
        }
        return head == tail ? 0 : tail - head + 1;
    }
}
